#include <bits/stdc++.h>

using namespace std;
/* 
在递增有序的单链表中插入元素x，
并保证插入后链表依然有序
 */
typedef struct lnode
{
    int data;
    struct lnode *next;
} lnode, *linklist;

// 原链表递增有序
int a[4] = {5, 6, 7, 8};
int n = 4;
void buildlist(linklist &L)
{
    L = (linklist)malloc(sizeof(lnode));
    lnode *r = L, *s;
    for (int i = 0; i < n; i++)
    {
        s = (lnode *)malloc(sizeof(lnode));
        s->data = a[i];
        r->next = s;
        r = r->next;
    }
    r->next = NULL;
}
void printlist(linklist L)
{
    lnode *s = L->next;
    while (s)
    {
        cout << s->data << " ";
        s = s->next;
    }
    cout << endl;
}
// 插入x使链表依然递增有序
void insert(linklist &l, int x)
{
    lnode *pre = l, *p = pre->next;
    // 新建结点
    lnode *s = (lnode *)malloc(sizeof(lnode));
    s->data = x;
    // 新建结点的时候要初始化next指针为空否则可能会产生异常
    s->next = NULL;
    //寻找合适的插入位置
    while (p)
    {
        if (p->data >= x)
        {
            // 如果找到一个结点比不小于x则将x插入到这个结点的前面
            pre->next = s;
            s->next = p;
            return;
        }
        // 否则指针继续向后扫描
        p = p->next;
        pre = pre->next;
        if (p == NULL)
        {
            // 如果扫描到最后一个元素也没有找到合适的位置则说明所有的结点都比x小，
            // 这时直接将新结点插入到尾部
            pre->next = s;
            return;
        }
    }
}
int main(int argc, char const *argv[])
{
    linklist l;
    buildlist(l);
    printlist(l);
    insert(l, 4);
    printlist(l);
    insert(l, 9);
    printlist(l);
    system("pause");
    return 0;
}
